package com.practice.niuke.new_direct_basics.class06;

import java.util.HashSet;
import java.util.Stack;

/**
 * 图的深度优先遍历：
 *
 * 1， 利用栈实现
 * 2， 从源节点开始把节点按照深度放入栈， 然后弹出
 * 3， 每弹出一个点， 把该节点下一个没有进过栈的邻接点放入栈
 * 4， 直到栈变空
 */
public class Code02_DFS {

    /**
     * 从node出发，进行深度优先遍历
     *
     * @param node 开始遍历的源节点
     */
    public static void dfs(Node node) {
        if (node == null) {
            return;
        }
        // 1. 准备一个栈
        Stack<Node> stack = new Stack<>();
        // 2. 使用一个set结构做记录，避免一个节点重复进入栈
        HashSet<Node> set = new HashSet<>();
        // 3. 将开始遍历的源节点放入到栈中，只要一个节点进入栈，那么它也一定要到Set中进行注册（放入Set中）
        stack.add(node);
        set.add(node);
        // 4. 打印源节点
        System.out.println(node.value);
        // 5. 当栈不为空时
        while (!stack.isEmpty()) {
            // 5.1 从栈中弹出一个节点
            Node cur = stack.pop();
            // 5.2 将当前弹出的节点的孩子节点依次放入栈中（没有入过栈就入栈，进入过栈则不用再进栈）
            for (Node next : cur.nexts) {
                // 5.2.1 之前没有进过栈
                if (!set.contains(next)) {
                    // 5.2.1.1 把自己压回栈
                    stack.push(cur);
                    // 5.2.1.2 把当前这个没有进入过栈的邻居节点压入栈，并在Set中注册，
                    stack.push(next);
                    set.add(next);
                    // 5.2.1.3 并且打印这个节点
                    System.out.println(next.value);
                    // 退出当前for循环，进行下一次的while循环再从栈中弹出一个当前节点
                    break;
                }
            }
        }
    }

}
